#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>

using namespace std;
typedef struct atreeNode
{
    int data;
    int height;
    struct atreeNode* left, *right;
    int ltag,rtag;
}treeNode,*PTN;

//iterative遍历 前中后
void PreOrder_Iterative(treeNode *root);
void PostOrder_Iterative(treeNode *root);
void InOrder_Iterative(treeNode *root);
void levelOrder(treeNode *root);

//AVL树
int max(int a,int b){
    return a>b?a:b;
}
int height(treeNode *root);
treeNode *newNode(int val);
int getBalanceFactor(treeNode *node);
treeNode *rightRotate(treeNode *y);
treeNode *leftRotate(treeNode *y);
treeNode *insert(treeNode* node, int val);



//线索化
/*2.初始化tag*/
void InitThread(treeNode& T) {
	if (T != NULL) {
		T->ltag = 0;
		T->rtag = 0;	//初始化当前树中的tag指针为0，表示还未线索化
		InitThread(T->left);	//递归遍历左子树
		InitThread(T->rright);	//递归遍历右子树
	}
}

treeNode *InThread(treeNode p,treeNode &pre){
    InThread(p);
    if(p->left==NULL){//p的前驱节点线索化
        p->left=pre;
        p->ltag=1;
    }
    if(pre!=NULL && pre->right == NULL){//pre的后继节点线索化
        pre->right=p;
        pre->rtag=1;
    }
    pre=p;
    InThread(p);
}
//防止爱的魔力转圈圈问题
treeNode *PreThread(treeNode p,treeNode &pre){
    if(p->left==NULL){
        p->left=pre;
        p->ltag=1;
    }
    if(pre!=NULL && pre->right == NULL){
        pre->right=p;
        pre->rtag=1;
    }
    pre=p;//一定要记住！！
    if(p->ltag==0)//防止将线索化的前驱当作p的左孩子导致再次传同样的p给PreThread()
        PreThread(p->left,pre);
    PreThread(p->right,pre);
}
treeNode *PostThread(treeNode p,treeNode &pre){
    PostThread(p->left,pre);
    PostThread(p->right,pre);
    if(p->left==NULL){
        p->left=pre;
        p->ltag=1;
    }
    if(pre!=NULL && pre->right == NULL){
        pre->right=p;
        pre->rtag=1;
    }
    pre=p;
}
treeNode *CreateInThreadTree(treeNode p){
    treeNode *pre=NULL;
    if(p==NULL) return p;
    InThread(p,pre);
    pre->rchild=NULL;//处理遍历的最后一个节点
    pre->rtag=1;
}
treeNode *CreatePreThreadTree(treeNode p){
    treeNode *pre=NULL;
    if(p==NULL) return p;
    PreThread(p,pre);
    if(pre->right == NULL)
        pre->rtag=1;//处理遍历的最后一个没线索化的空指针节点 ？？？？？？
//例如：
/*
          a
        /   \ 
       Q     b(pre)
            / 
           c(p) 
              
          a
        /   \ 
       Q     b
            / \
           c    e(pre)(p)
*/
}

treeNode *CreatePostThreadTree(treeNode p){
    treeNode *pre=NULL;
    if(p==NULL) return p;
    PostThread(p,pre);
    if(pre->right==NULL)
        pre->rtag=1;//处理遍历的最后一个没线索化的空指针节点 ？？？？？？
//例如:
/*
          a(p)(pre)
        /   \
       b
      /
     Q
*/
}

int main(){
    treeNode* root = NULL;
	int array[6] = { 10,20,30,40,50,25};
	for (int i = 0;i < 6;i++)
	{
		root=insert(root, array[i]);
	}
    /*
     * 树的结构如下:
           30
        /      \
      20       40
     /  \        \
    10   25       50
    */ 
    printf("前序遍历（迭代版）:");
    PreOrder_Iterative(root);
    printf("\n后序遍历（迭代版）:");
    PostOrder_Iterative(root);
    printf("\n中序遍历（迭代版）:");
    InOrder_Iterative(root);
    printf("\n层次遍历:");
    levelOrder(root);
    return 0;
}

//辅助函数：计算树的高度
int height(treeNode *root){
    if(NULL==root)
        return 0;
    return 1+max(height(root->left),height(root->right));
}
//辅助函数：创建新节点
treeNode *newNode(int val){ 
    treeNode *node=(treeNode *)malloc(sizeof(treeNode)*1);
    node->data=val;
    node->left=NULL;
    node->right=NULL;
    node->height=0;//一定记住
    return node;
}
//辅助函数：获取节点的平衡因子
int getBalanceFactor(treeNode *node){
    if(NULL==node){
        return 0;
    }
    return height(node->left)-height(node->right);
}
//右旋
treeNode *rightRotate(treeNode *y){
    /*
     * 树的结构示意图
            y node
           / \
          x   0
         / \
    val 0+1 0
    */
    treeNode *x=y->left;
    treeNode *xr=x->right;
    //旋转
    x->right=y;
    y->left=xr;
    //更新节点高度
    x->height=height(x);
    y->height=height(y);
    //返回旋转后的根节点
    return x;

}
//左旋
treeNode *leftRotate(treeNode *y){
    /*
     * 树的结构示意图
            y node
           / \
          0   x
             / \
            0   0+1 val
    */
   treeNode *x=y->right;
   treeNode *xl=x->left;
   //旋转
   x->left=y;
   y->right=xl;
   //更新节点的高度
   x->height=height(x);
   y->height=height(y);
   //返回旋转后的根节点
   return x;
}
/*
*@brief 向以node为根节点的树中插入val
*
*@param node根节点
*@param val 待插入的值
*@param treeNode* 插入后该树新的根节点
*/
treeNode *insert(treeNode* node, int val)
{
	//1.按照BST的规律在每个叶子节点上插入新的值
    if(NULL==node)
        return newNode(val);
    if(val<node->data)
        node->left=insert(node->left,val);
    else if(val>node->data)
        node->right=insert(node->right,val);
    else
        return node;
    //2.更新插入路径上每棵子树的高度
    node->height=height(node);
    //3.计算平衡因子
    int bf=getBalanceFactor(node);
    //LL不平衡
    if(bf>1 && val<node->left->data){//插入的节点在 最小不平衡子树的父节点 的左孩子的左侧
        return rightRotate(node);
    }
    //RR型
    if(bf<-1 && val>node->right->data){
        return leftRotate(node);
    }
    //LR
    if(bf>1 && val>node->left->data){//插入的节点在 最小不平衡子树父节点 的左孩子的右侧
        node->left=leftRotate(node->left);
        return rightRotate(node);
    }
    //RL型
    if(bf<-1 && val<node->right->data){
        node->right=rightRotate(node->right);
        return leftRotate(node);
    }
    //平衡
    return node;
}
/*
* 非递归先序遍历
* 借助栈实现
*/
void PreOrder_Iterative(treeNode *root){
    if(NULL==root){
        printf("空树一棵！");
        return; //空树
    }
    stack<treeNode *> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){//栈非空
        treeNode *node = nodeStack.top();//保存栈顶结点
        printf("%d ",node->data);//访问栈顶元素
        nodeStack.pop();//删除栈顶元素
        //删除元素的右左孩子入栈
        if(node->right) nodeStack.push(node->right);
        if(node->left) nodeStack.push(node->left);   
    }

}
/*
* 非递归中序遍历
* 借助栈实现,curNode指针
*/
void InOrder_Iterative(treeNode *root){
    if(NULL==root)
        return;//空树
    stack<treeNode *>nodeStack;
    PTN curNode=root;//维护一个当前节点指针
    //当前节点指针非空，或栈非空时迭代处理
    while(curNode||!nodeStack.empty()){
        //当前节点非空，沿着左子树方向入栈
        while(curNode){
            nodeStack.push(curNode);
            curNode=curNode->left;
        }
        //此时栈顶没有左子树，或者左子树已经访问完
        curNode=nodeStack.top();//取栈顶节点
        printf("%d ",curNode->data);//访问栈顶节点
        nodeStack.pop();//从栈中删除被访问元素
        curNode=curNode->right;//当前节点设为右节点
    }
}
/*
* 非递归后序遍历
* 先序：根 左 右 
* 后序：左 右 根
* 通过对先序遍历时左右孩子入栈顺序进行调整（先左孩子入栈再右孩子入栈得到 "根右左"的遍历序列），将结果在通过一遍栈可以得到后序遍历。
* 借助两个栈实现
*/
void PostOrder_Iterative(treeNode* root){
    if(NULL==root)
        return ;
    stack<treeNode*> nodeStack;
    stack<treeNode*> resStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        treeNode *node=nodeStack.top();//保存栈顶节点，便于寻找左右孩子
        //printf("%d ",node->data);
        resStack.push(node);
        nodeStack.pop();
        if(node->left) nodeStack.push(node->left);
        if(node->right) nodeStack.push(node->right); 
    }
    while(!resStack.empty()){
        printf("%d ",resStack.top()->data);
        resStack.pop();
    }
}
/*
* 借助队列
*/
void levelOrder(treeNode *root){
    if(NULL==root) 
        return;
    queue<treeNode *> nodeQueue;
    nodeQueue.push(root);
    while(!nodeQueue.empty()){
        treeNode *node=nodeQueue.front();
        printf("%d ",node->data);
        if(node->left) nodeQueue.push(node->left);
        if(node->right) nodeQueue.push(node->right);
        nodeQueue.pop();
    }
}